package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func (n *ListNode) String() string {
	return fmt.Sprintf("%d", n.Val)
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	head := &ListNode{Val: 0}
	// carry 表示进位
	n1, n2, carry, current := 0, 0, 0, head
	for l1 != nil || l2 != nil || carry != 0 {
		if l1 == nil {
			n1 = 0
		} else {
			n1 = l1.Val
			l1 = l1.Next
		}
		if l2 == nil {
			n2 = 0
		} else {
			n2 = l2.Val
			l2 = l2.Next
		}
		// 计算下一个节点的值
		current.Next = &ListNode{Val: (n1 + n2 + carry) % 10}
		current = current.Next
		// 计算进位
		carry = (n1 + n2 + carry) / 10
		fmt.Println(n1, n2, carry, current)
	}
	return head.Next
}

// 基本思路：使用 carry 表示进位，使用 current 表示当前节点，使用 head 表示头节点
// 1. 遍历两个链表，将两个链表中的节点的值相加，得到的值作为 current 的值
// 2. 将 current 的值除以 10，得到的商作为 carry，余数作为 current 的值
// 3. 将 current 的值作为下一个节点的值，将 carry 作为下一个节点的值
// 4. 将 current 指向 next
func main() {
	// 创建第一个链表: l1 = [2,4,3]
	l1 := &ListNode{Val: 2}
	l1.Next = &ListNode{Val: 4}
	l1.Next.Next = &ListNode{Val: 3}

	// 创建第二个链表: l2 = [5,6,4]
	l2 := &ListNode{Val: 5}
	l2.Next = &ListNode{Val: 6}
	l2.Next.Next = &ListNode{Val: 4}

	// 使用 -> 打印链表
	printList(l1)
	printList(l2)

	l3 := addTwoNumbers(l1, l2)
	printList(l3)
}

// 打印链表，使用 -> 连接节点
func printList(head *ListNode) {
	current := head
	for current != nil {
		fmt.Print(current.Val)
		if current.Next != nil {
			fmt.Print(" -> ")
		}
		current = current.Next
	}
	fmt.Println()
}
